#include <algorithm>
#include <vector>
using namespace std;
int maxSubArray(vector<int> &nums) {
  int n = nums.size();
  vector<int> dp(n, 0);
  dp[0] = nums[0];
  int maxValue = nums[0];
  for (int i = 1; i < n; i++) {
    // 数组[0,i]的最大长连续和为数组[0,i-1]和[0,i-1]+nums[i]中最大的值
    dp[i] = max(dp[i - 1] + nums[i], dp[i - 1]);
    maxValue = max(dp[i], maxValue);
  }
  return maxValue;
}